COCI/2010-2011/Contest #1 - 22.10.2010/matrix/matrix.cpp

   1 // Andrés Mejía
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const double EPS = 1e-9;
  29 int cmp(double x, double y = 0, double tol = EPS) {
  30     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  31 }
  32
  33 const int MAXN = 405;
  34 int mat[MAXN][MAXN];
  35
  36 vector<int> A[2 * MAXN], B[2 * MAXN];
  37
  38 int main(){
  39     int n;
  40     scanf("%d", &n);
  41     for (int i = 0; i < n; ++i) {
  42         for (int j = 0; j < n; ++j) {
  43             scanf("%d", &mat[i][j]);
  44         }
  45     }
  46
  47     for (int k = 0; k < n; ++k) {
  48         int i = n - k - 1, j = 0;
  49         A[k].push_back(0);
  50         while (i < n and j < n) {
  51             A[k].push_back(mat[i][j] + A[k].back());
  52             i++; j++;
  53         }
  54     }
  55
  56     for (int k = 1; k < n; ++k) {
  57         int i = 0, j = k;
  58         A[n - 1 + k].push_back(0);
  59         while (i < n and j < n) {
  60             A[n - 1 + k].push_back(mat[i][j] + A[n - 1 + k].back());
  61             i++; j++;
  62         }
  63     }
  64
  65     for (int k = 0; k < n; ++k) {
  66         int i = 0, j = k;
  67         B[k].push_back(0);
  68         while (i < n and j >= 0) {
  69             B[k].push_back(mat[i][j] + B[k].back());
  70             i++; j--;
  71         }
  72     }
  73
  74     for (int k = 1; k < n; ++k) {
  75         int i = k, j = n - 1;
  76         B[n - 1 + k].push_back(0);
  77         while (i < n and j >= 0) {
  78             B[n - 1 + k].push_back(mat[i][j] + B[n - 1 + k].back());
  79             i++; j--;
  80         }
  81     }
  82
  83     // For(k, 0, 2 * n - 1) {
  84     //     printf("A[k=%d]: ", k);
  85     //     For(i, 0, A[k].size()) printf("%d ", A[k][i]);
  86     //     puts("");
  87     // }
  88     // For(k, 0, 2 * n - 1) {
  89     //     printf("B[k=%d]: ", k);
  90     //     For(i, 0, B[k].size()) printf("%d ", B[k][i]);
  91     //     puts("");
  92     // }
  93
  94
  95
  96     int ans = 0;
  97     for (int i = 0; i < n; ++i) {
  98         for (int j = 0; j < n; ++j) {
  99             for (int delta = 0; i + delta < n and j + delta < n; ++delta) {
 100                 int ka = n - 1 - i + j;
 101                 int kb = i + j + delta;
 102
 103                 int sumA = A[ka].at( min(i, j) + delta + 1 ) - A[ka].at( min(i, j) );
 104                 int sumB = B[kb].at( min(i, n - 1 - j - delta) + delta + 1 ) - B[kb].at( min(i, n - 1 - j - delta) );
 105
 106                 if (sumA - sumB > ans) {
 107                     //printf("new best sum from [%d, %d] and delta = %d, (sumA = %d, sumB = %d, i + delta =%d, j + delta = %d)\n", i, j, delta, sumA, sumB, i + delta, j + delta);
 108                     ans = sumA - sumB;
 109                 }
 110             }
 111         }
 112     }
 113     cout << ans << endl;
 114     return 0;
 115 }